﻿#include"stdafx.h"
#include"HeapSort.h"

void HeapSort::Shift(int left, int right)
{
	int x, curr, joint;
	curr = left; joint =2*curr+1;// a joint: Phần tử liên đới
	x = a[curr];
	while (joint <= right)
	{
		if (joint < right)// nếu có đủ 2 phần tử liên đới
		{ 
			if (a[joint] < a[joint+1]) //xác định phần tử liên đới lớn nhất
			{
				joint = joint+1;
			}
		}
		
		if (a[joint]<x)
		{
			break; // Thỏa quan hệ liên đới
		}

			a[curr] = a[joint];
			curr = joint;// Xét khả năng hiệu chỉnh lan truyền
			joint = 2*curr+1;
	}
	a[curr] = x;
}

void HeapSort::CreateHeap()
{
	int l;
	l = (8-1)/2; // a[l] là phần tử ghép thêm
	while (l>=0) 
	{
		Shift(l,8);
		l = l-1;
	}
}

void HeapSort::Heap_Sort()
{
	int r;
	CreateHeap();
	r = 8-1; // r là vị trí đúng cho phần tử nhỏ nhất
	while(r>=0) 
	{
		Swap(a[0],a[r]);
		r = r-1;
		Shift(0,r);
	}
}

